import java.util.Arrays;

public class Heap {
    public int[] elem;
    public int usedSize;

    public Heap() {
        this.elem = new int[10];
    }

    //创建一个大根堆
    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
        //从最后一个根节点开始
        //usedSize - 1 是最后一个节点的下标
        //((usedSize - 1) - 1) / 2是这个节点的父节点 也就是最后一个父节点
        //从这个节点开始对每棵树进行调整
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent --){
            shiftDown(parent,usedSize);
        }
    }

    /**
     * @param parent 每棵子树的根节点
     * @param len    代表每棵子树的结束位置
     */
    //
    private void shiftDown(int parent, int len) {
        int child = 2 * parent + 1;
        //左孩子节点的下标
        while (child < len) {
            //if的目的是找出左右孩子中较大的那个孩子的下标
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                //child + 1 < len 的目的是保证右节点也在下标的范围内 防止数组越界
                //elem[child] < elem[child + 1]
                child = child + 1;
            }
            //if的目的是判断较大的那个孩子节点有没有父节点大
            if (elem[child] > elem[parent]) {
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                //将其中较大的放在根位置
                parent = child;
                child = 2 * parent + 1;
                //此时这棵树调整完整 在调整下一颗；
            } else {
                break;
                //此时就是大根堆
            }
        }
    }

    //向上调整
    public void shiftUp(int child){
        int parent = (child - 1) / 2;
        while (child > 0){
            if(elem[child] > elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }

    public void push(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,2 * elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
        shiftUp(usedSize - 1);
        //每添加一个元素 就向上调整一次 保证还是大根堆；
    }

    private boolean isFull(){
        return this.usedSize == elem.length;
    }

    public int poll(){
        if(empty()){
            throw new HeapEmptyException("优先级队列为空");
        }
        int temp = elem[0];
        elem[0] = elem[usedSize - 1];
        elem[usedSize - 1] =temp;
        usedSize --;
        shiftDown(0,usedSize);
        return temp;
        /**
         * 逻辑为：
         * poll方法的功能为弹出下标为0的元素
         * 但是我们是优先级队列 弹出第一个元素整棵树就不是堆
         * 我们就把第一个元素和最后一个元素交换 然后使usedSize-- 来删除第一个元素
         * 返回第一个元素 在向下调整根节点对应的树
         *
         */

    }

    private boolean empty(){
        return this.usedSize == 0;
    }

    public int peek(){
        if(empty()){
            throw new HeapEmptyException("优先级队列为空");
        }
        return elem[0];
    }
}





























